package kmp;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 给定一个经过编码的字符串，返回它解码后的字符串。
 *
 * 编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
 *
 * 你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
 *
 * 此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
 * 示例 1：
 *
 * 输入：s = "3[a]2[bc]"
 * 输出："aaabcbc"
 * 示例 2：
 *
 * 输入：s = "3[a2[c5[b]]]"
 * 输出："accaccacc"
 * 示例 3：
 *
 * 输入：s = "2[abc]3[cd]ef"
 * 输出："abcabccdcdcdef
 *
 */
public class leetCode394_decodeString {
    public static void main(String[] args) {
        leetCode394_decodeString a= new leetCode394_decodeString();
        a.decodeString("3[a2[c5[b]]]");
    }
    public String decodeString(String s) {
        Deque<Integer> countQueue = new LinkedList<>();
        Deque<StringBuilder> sbQueue = new LinkedList<>();
        int count = 0;
        StringBuilder sb = new StringBuilder();
        for (char c : s.toCharArray()) {
            if(Character.isDigit(c)){
                count = count * 10 + c - '0';
            }else if(c == '['){
                countQueue.push(count);
                sbQueue.push(sb);
                count = 0;
                sb = new StringBuilder();
            }else if(c == ']'){
                StringBuilder temp = sbQueue.pop();
                Integer tmpCount = countQueue.pop();
                for (int i = 0; i < tmpCount; i++) {
                    temp.append(sb);
                }
                sb = temp;
            }else{
                sb.append(c);
            }

        }
        return sb.toString();
    }
}
